package com.example.common;

import com.alibaba.fastjson.JSON;

/**
 * @author dangwen1
 * @date 2022年01月06日 15:54
 * @description 插入排序的进化版
 */
public class Shell {
    public static void main(String[] args) {
        int[] arr = new int[]{1,21,2134,231,312,4,45,65,9,67,8,8,};
        int len = arr.length;
        for (int gap = (int) Math.floor(len / 2); gap > 0; gap = (int)Math.floor(gap / 2)) {
            // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
            for (int i = gap; i < len; i++) {
                int j = i;
                int current = arr[i];
                while (j - gap >= 0 && current < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }
                arr[j] = current;
            }
        }
        System.out.println(JSON.toJSONString(arr));
    }
}
